package com.ly.algorithm.offerpointer;

/**
 * @Classname Offer24
 * @Description TODO
 * @Date 2021/1/27 15:38
 * @Author 冷心影翼
 */
public class Offer24 {

    public static void main(String[] args) {
        Solution24 solution24 = new Solution24();
        solution24.reverseList(ListNode.init(new int[]{1,2,3})).printRes();
        solution24.reverseListTwoPoint(ListNode.init(new int[]{1,2,3})).printRes();
        solution24.reverseListByRecursion(ListNode.init(new int[]{1,2,3})).printRes();
    }

}


class Solution24 {

    //头插
    public ListNode reverseList(ListNode head) {
        ListNode newHead = new ListNode(-1);
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = newHead.next;
            newHead.next = cur;
            cur = next;
        }
        return newHead.next;
    }


    //双指针
    public ListNode reverseListTwoPoint(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    //递归
    public ListNode reverseListByRecursion(ListNode head) {
        return reverseListByRecursion(null,head);
    }

    private ListNode reverseListByRecursion(ListNode pre, ListNode cur) {
        if(cur == null) {
            return pre;
        }
        ListNode res = reverseListByRecursion(cur,cur.next);
        cur.next = pre;
        return res;
    }
}